/*
 *  linux/kernel/sched.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 * 'sched.c' is the main kernel file. It contains scheduling primitives
 * (sleep_on, wakeup, schedule etc) as well as a number of simple system
 * call functions (type getpid(), which just extracts a field from
 * current-task
 */
#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h>
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h>

#include <signal.h>

#define _S(nr) (1<<((nr)-1))
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))

void show_task(int nr,struct task_struct * p)
{
	int i,j = 4096-sizeof(struct task_struct);

	printk("%d: pid=%d, state=%d, ",nr,p->pid,p->state);
	i=0;
	while (i<j && !((char *)(p+1))[i])
		i++;
	printk("%d (of %d) chars free in kernel stack\n\r",i,j);
}

void show_stat(void)
{
	int i;

	for (i=0;i<NR_TASKS;i++)
		if (task[i])
			show_task(i,task[i]);
}

#define LATCH (1193180/HZ)

extern void mem_use(void);
// 具体实现是在汇编中，链接器会将其链接进来
extern int timer_interrupt(void);
extern int system_call(void);

union task_union {
	struct task_struct task;
	char stack[PAGE_SIZE];
};

static union task_union init_task = {INIT_TASK,};

long volatile jiffies=0;
long startup_time=0;
struct task_struct *current = &(init_task.task);
struct task_struct *last_task_used_math = NULL;

struct task_struct * task[NR_TASKS] = {&(init_task.task), };

long user_stack [ PAGE_SIZE>>2 ] ;

struct {
	long * a;
	short b;
	} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
/*
 *  'math_state_restore()' saves the current math information in the
 * old math state array, and gets the new ones from the current task
 */
void math_state_restore()
{
	if (last_task_used_math == current)
		return;
	__asm__("fwait");
	if (last_task_used_math) {
		__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
	}
	last_task_used_math=current;
	if (current->used_math) {
		__asm__("frstor %0"::"m" (current->tss.i387));
	} else {
		__asm__("fninit"::);
		current->used_math=1;
	}
}

/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
// 核心任务：从所有可运行（TASK_RUNNING）的进程中选择一个 counter 值最大的进程，切换到该进程执行。
// 触发时机
// 进程时间片用完（do_timer() 中调用）。
//
// 进程主动让出 CPU（如 sleep() 或 pause()）。
//
// 中断返回到用户态时（若当前进程需要被抢占）。
void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

    // 检查定时器信号和唤醒进程
    // 若进程设置的 alarm 时间已到（alarm < jiffies），向进程发送 SIGALRM 信号（信号位掩码操作）
    // 如果进程处于 TASK_INTERRUPTIBLE 状态且收到未被阻塞的信号（如 SIGINT），则将其状态改为 TASK_RUNNING（可调度）
	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
            // 检查 alarm 定时器是否到期
			if ((*p)->alarm && (*p)->alarm < jiffies) {
					(*p)->signal |= (1<<(SIGALRM-1)); // 发送 SIGALRM 信号
					(*p)->alarm = 0;
				}
            // 检查是否有未阻塞的信号唤醒进程
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING; // 将可中断睡眠进程设为就绪态
		}

/* this is the scheduler proper: */

    // 调度器核心逻辑
    // 进程选择规则：
    // 遍历进程数组 task[]，选择 state == TASK_RUNNING 且 counter 最大的进程。
    // 若存在 counter > 0 的进程，立即选中（next = i）。
    // 若所有就绪进程的 counter = 0，则按公式重新计算 counter：
	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
        // // 遍历所有进程，选择 counter 最大的就绪进程
		while (--i) {
			if (!*--p)
				continue;
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}
        // 找到有效进程则退出循环
		if (c) break;
        // 所有进程 counter=0，重新分配时间片
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
                // priority：进程的静态优先级（通常为 15），保证每个进程至少能分到时间片。
                // counter >> 1：衰减历史 counter，避免饥饿。
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
    // 切换进程
    // 是一个宏（定义在 sched.h 中），通过 ljmp 指令切换任务状态段（TSS），触发 CPU 上下文切换。
    // 保存当前进程的寄存器状态，加载目标进程的 TSS 和 LDT。
	switch_to(next);
}

int sys_pause(void)
{
	current->state = TASK_INTERRUPTIBLE;
	schedule();
	return 0;
}

void sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;

	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp = *p;
	*p = current;
	current->state = TASK_UNINTERRUPTIBLE;
	schedule();
	if (tmp)
		tmp->state=0;
}

void interruptible_sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;

	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp=*p;
	*p=current;
repeat:	current->state = TASK_INTERRUPTIBLE;
	schedule();
	if (*p && *p != current) {
		(**p).state=0;
		goto repeat;
	}
	*p=NULL;
	if (tmp)
		tmp->state=0;
}

void wake_up(struct task_struct **p)
{
	if (p && *p) {
		(**p).state=0;
		*p=NULL;
	}
}

/*
 * OK, here are some floppy things that shouldn't be in the kernel
 * proper. They are here because the floppy needs a timer, and this
 * was the easiest way of doing it.
 */
static struct task_struct * wait_motor[4] = {NULL,NULL,NULL,NULL};
static int  mon_timer[4]={0,0,0,0};
static int moff_timer[4]={0,0,0,0};
unsigned char current_DOR = 0x0C;

int ticks_to_floppy_on(unsigned int nr)
{
	extern unsigned char selected;
	unsigned char mask = 0x10 << nr;

	if (nr>3)
		panic("floppy_on: nr>3");
	moff_timer[nr]=10000;		/* 100 s = very big :-) */
	cli();				/* use floppy_off to turn it off */
	mask |= current_DOR;
	if (!selected) {
		mask &= 0xFC;
		mask |= nr;
	}
	if (mask != current_DOR) {
		outb(mask,FD_DOR);
		if ((mask ^ current_DOR) & 0xf0)
			mon_timer[nr] = HZ/2;
		else if (mon_timer[nr] < 2)
			mon_timer[nr] = 2;
		current_DOR = mask;
	}
	sti();
	return mon_timer[nr];
}

void floppy_on(unsigned int nr)
{
	cli();
	while (ticks_to_floppy_on(nr))
		sleep_on(nr+wait_motor);
	sti();
}

void floppy_off(unsigned int nr)
{
	moff_timer[nr]=3*HZ;
}

void do_floppy_timer(void)
{
	int i;
	unsigned char mask = 0x10;

	for (i=0 ; i<4 ; i++,mask <<= 1) {
		if (!(mask & current_DOR))
			continue;
		if (mon_timer[i]) {
			if (!--mon_timer[i])
				wake_up(i+wait_motor);
		} else if (!moff_timer[i]) {
			current_DOR &= ~mask;
			outb(current_DOR,FD_DOR);
		} else
			moff_timer[i]--;
	}
}

#define TIME_REQUESTS 64

static struct timer_list {
	long jiffies;
	void (*fn)();
	struct timer_list * next;
} timer_list[TIME_REQUESTS], * next_timer = NULL;

void add_timer(long jiffies, void (*fn)(void))
{
	struct timer_list * p;

	if (!fn)
		return;
	cli();
	if (jiffies <= 0)
		(fn)();
	else {
		for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
			if (!p->fn)
				break;
		if (p >= timer_list + TIME_REQUESTS)
			panic("No more time requests free");
		p->fn = fn;
		p->jiffies = jiffies;
		p->next = next_timer;
		next_timer = p;
		while (p->next && p->next->jiffies < p->jiffies) {
			p->jiffies -= p->next->jiffies;
			fn = p->fn;
			p->fn = p->next->fn;
			p->next->fn = fn;
			jiffies = p->jiffies;
			p->jiffies = p->next->jiffies;
			p->next->jiffies = jiffies;
			p = p->next;
		}
	}
	sti();
}

void do_timer(long cpl)
{
    // 控制 PC 扬声器的蜂鸣时间。
	extern int beepcount;
	extern void sysbeepstop(void);

    // beepcount 是蜂鸣计数器，每次时钟中断减 1，归零时调用 sysbeepstop() 停止蜂鸣。
    // 典型用途：内核调试或报警（如 printk 打印错误时触发蜂鸣）
	if (beepcount)
		if (!--beepcount)
			sysbeepstop();

    // 用于区分统计用户态和内核态的 CPU 时间
    // cpl = 0 表示中断发生时 CPU 处于 内核态。
    // cpl > 0 表示中断发生时 CPU 处于 用户态。
    //
    // 用途：用于 top、ps 等工具统计进程的 CPU 占用率。
    // 如果当前是用户态，就进程的用户态时间滴答加1
	if (cpl)
        // 进程在用户态消耗的时钟滴答数
		current->utime++;
	else
        // 进程在内核态消耗的时钟滴答数。
        // 否则 进程的系统态时间滴答加1
		current->stime++;

    // 处理内核定时器（next_timer）
    // 定时器链表：next_timer 指向一个按 jiffies 排序的链表，每次中断递减计时
    // 触发逻辑：
    //
    // 若 jiffies <= 0，执行回调函数 fn()（如进程睡眠唤醒、超时任务）
    // 链表的插入和排序由 add_timer() 实现（未在此代码中展示）
    // 用途：实现 sleep()、定时任务等。
	if (next_timer) {
		next_timer->jiffies--;
		while (next_timer && next_timer->jiffies <= 0) {
			void (*fn)(void);
			
			fn = next_timer->fn;
			next_timer->fn = NULL;
			next_timer = next_timer->next;
			(fn)();  // 执行定时器回调函数
		}
	}
	if (current_DOR & 0xf0)
		do_floppy_timer();
    // 当前线程还有剩余时间片，直接返回
	if ((--current->counter)>0) return;
	current->counter=0;
	if (!cpl) return;
    // 若没有剩余时间片，调度
	schedule();
}

int sys_alarm(long seconds)
{
	int old = current->alarm;

	if (old)
		old = (old - jiffies) / HZ;
	current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
	return (old);
}

int sys_getpid(void)
{
	return current->pid;
}

int sys_getppid(void)
{
	return current->father;
}

int sys_getuid(void)
{
	return current->uid;
}

int sys_geteuid(void)
{
	return current->euid;
}

int sys_getgid(void)
{
	return current->gid;
}

int sys_getegid(void)
{
	return current->egid;
}

int sys_nice(long increment)
{
	if (current->priority-increment>0)
		current->priority -= increment;
	return 0;
}

void sched_init(void)
{
	int i;
    // typedef struct desc_struct {
    //	unsigned long a,b;
    //} desc_table[256]
	struct desc_struct * p;

	if (sizeof(struct sigaction) != 16)
		panic("Struct sigaction MUST be 16 bytes");
    // FIRST_TSS_ENTRY =4
    // FIRST_LDT_ENTRY =5
    // TSS 叫任务状态段，就是保存和恢复进程的上下文的，所谓上下文，其实就是各个寄存器的信息而已，这样进程切换的时候，才能做到保存和恢复上下文，继续执行
    // 往全局描述符中添加 TSS 段，索引是 4
	set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
    // LDT 叫局部描述符表，是与 GDT 全局描述符表相对应的，内核态的代码用 GDT 里的数据段和代码段，而用户进程的代码用每个用户进程自己的 LDT 里得数据段和代码段
    // 往全局描述符中添加 LDT 段，索引是 5
	set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
	// 全局描述符表中的每一个元素 8个字节，而desc_struct 也是8个字节，这里 p指向全局描述符的第6个索引
    p = gdt+2+FIRST_TSS_ENTRY;
    // NR_TASKS =64 linux0.11版本认为最多64 个进程
    // 这段代码有个循环，干了两件事。
    // 一个是给一个长度为 64，结构为 task_struct 的数组 task 附上初始值
	for(i=1;i<NR_TASKS;i++) {
        // struct task_struct * task[NR_TASKS] = {&(init_task.task), }
		task[i] = NULL;
        // 下面也是给对应的进程在 全局描述符表中 添加两个段， tss段和 ldt段，并且初始化为0
        // 这个循环做的另一件事，是给 gdt 剩下的位置填充上 0，也就是把剩下留给 TSS 和 LDT 的描述符都先附上空值
		p->a=p->b=0;
		p++;
		p->a=p->b=0;
		p++;
	}
/* Clear NT, so that we won't have troubles with that later on */
	__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
    // #define _TSS(n) ((((unsigned long) n)<<4)+(FIRST_TSS_ENTRY<<3))
    // #define _LDT(n) ((((unsigned long) n)<<4)+(FIRST_LDT_ENTRY<<3))
    // #define ltr(n) __asm__("ltr %%ax"::"a" (_TSS(n)))
    // #define lldt(n) __asm__("lldt %%ax"::"a" (_LDT(n)))
    // CPU 之后就能通过 tr 寄存器找到 当前进程 的任务状态段信息，也就是上下文信息，以及通过 ldt 寄存器找到 当前进程 在用的局部描述符表信息
    // ltr 是给 tr 寄存器赋值，以告诉 CPU 任务状态段 TSS 在内存的位置，这里的tss是全局描述符中的第四个索引的tss
	ltr(0);
    // lldt 一个是给 ldt 寄存器赋值，以告诉 CPU 局部描述符 LDT 在内存的位置，这里的 ldt是全局描述符中的第5个索引的ldt
	lldt(0);

    // 四行端口读写代码，两行设置中断代码。
    // 端口读写我们已经很熟悉了，就是 CPU 与外设交互的一种方式，之前讲硬盘读写以及 CMOS 读写时，已经接触过了
    // 这次交互的外设是一个可编程定时器的芯片，这四行代码就开启了这个定时器，
    // 之后这个定时器变会持续的、以一定频率的向 CPU 发出中断信号

    outb_p(0x36,0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
	outb_p(LATCH & 0xff , 0x40);	/* LSB */
	outb(LATCH >> 8 , 0x40);	/* MSB */
    // 第一个就是时钟中断，中断号为 0x20，中断处理程序为 timer_interrupt。
    // 那么每次定时器向 CPU 发出中断后，便会执行这个函数
    // 这个定时器的触发，以及时钟中断函数的设置，是操作系统主导进程调度的一个关键！
    // 没有他们这样的外部信号不断触发中断，操作系统就没有办法作为进程管理的主人，通过强制的手段收回进程的 CPU 执行权限
	set_intr_gate(0x20,&timer_interrupt);
	outb(inb_p(0x21)&~0x01,0x21);
    // 第二个设置的中断叫系统调用 system_call，中断号是 0x80，这个中断又是个非常非常非常非常非常非常非常重要的中断，
    // 所有用户态程序想要调用内核提供的方法，都需要基于这个系统调用来进行
	set_system_gate(0x80,&system_call);
}
